原始题目:剑指 Offer 22. 链表中倒数第k个节点 (opens new window)

解题思路:

使用快慢指针解决这个问题。

一开始快慢指针 fastfastslowslow 都指向链表表头,然后快指针 fastfast 先走 kk 步之后,slowslow 指针开始移动,两个指针同时移动。当 fastfast 到达重点时,slowslow 指针刚好到达倒数第 kk 个节点。

代码:

public ListNode getKthFromEnd(ListNode head, int k) {
    if (head == null || k <= 0) {
        return head;
    }
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && k-- > 0) {
        fast = fast.next;
    }
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

复杂度分析

  • 时间复杂度O(N)O(N)NN 为链表的节点个数,因为 fastfast 指针需要遍历全部的节点。
  • 空间复杂度O(N)O(N)fastfastslowslow 指针使用常数大小的额外空间。
上次更新: 2023/10/15